#include <cstdio>
#include <cstdlib>
#include <iostream>


#include "element.H"
#include "skiplist.H"
#include "tab_dynamique.H"
#include "Intervalle.H"

using namespace std;

SCellule *creerCellule()
{
    int i ;
    SCellule *cellule ;

    cellule = new SCellule ;
    cellule->info = 0 ;
    for (i=0;i<TAILLE_MAX;i++)
    {
        cellule->suivants[i]=NULL ;
    }

    cellule->niveauList = 0 ;

    return cellule ;
}

void testamentSCellule (SCellule *cellule)
{
    delete cellule ;
}

void testamentSListe (SListe *liste)
{
    SCellule *tmp ;
    while(liste->teteListe != NULL)
    {
        tmp=liste->teteListe ;
        liste->teteListe=liste->teteListe->suivants[0];
        testamentSCellule(tmp);
    }
    delete liste ;
}


SCellule *initialiserSCellule (const Elem valeur)
{
    SCellule *cellule ;
    cellule = creerCellule();
    cellule->info=valeur ;
    return cellule ;
}

void initialiserSCellulePF(SCellule *cellule)
{
    int pileOUface=rand() % 10 + 1;
    int i =0 ;
    while (pileOUface <=5 || i>15)
    {
        cellule->suivants[i]=NULL;
        cellule->niveauList++;
        i++;
        pileOUface=rand() % 10 + 1;
    }
}

SListe* CreationListe ()
{
    SListe *liste ;
    liste = new SListe;
    liste->teteListe = creerCellule();
    return liste ;
}

bool testSlisteVide(SListe *liste)
{

    if (liste->teteListe->suivants[0] == NULL)
    return true ;
    else
    return false ;
}

void afficheSListe (SListe *liste)
{
    if (testSlisteVide(liste))
        {
            cout<<"la liste est vide "<<endl;
        }
    else
    {
        int i ;
        SCellule *cellule ;
        for (i=liste->teteListe->niveauList; i >= 0;i--)
        {
            cellule=liste->teteListe->suivants[i];

            // on saute la cellule bidon

            cout << "niveau"<<i<<"\t";
            while(cellule != NULL)
            {

            //afficheElementInt(cellule->info);
            cout<<" "<<cellule->info;
            cellule=cellule->suivants[i];
            }
            cout<<endl ;
        }

    }

}
//void afficheSListe (SListe *liste)
//{
//    SCellule *cellule = liste->teteListe->suivants[0];
//    while (cellule != NULL)
//    {
//
//        afficheSCellule(cellule);
//        cellule=cellule->suivants[0];
//    }
//}


void afficheSCellule(SCellule *cellule)
{
    if(cellule== NULL )
        {
            cout <<"la cellule est vide ou n existe pas "<<endl;
        }
    else
    {
        cout<<"Niveau maximum de la cellule est "<<cellule->niveauList<<endl;
        for(int i=cellule->niveauList;i>=0;i--)
        {
            cout<<"Niveau :"<<i<<endl;
            cout<<cellule->info<<endl;
        }
    }

}





SCellule * rechercheElementSListe( SListe *liste , Elem e )
{
    if (testSlisteVide(liste))
        {
            cout<<"impossible de trouver "<<e<<" car la liste est vide "<<endl;
            return NULL ;
        }
    else
        {
            int i = liste->teteListe->niveauList-1 ;
            SCellule *tmp =rechercheElementSListeNiveau(liste->teteListe,liste->teteListe->suivants[i],e,i);
            //cout<<"le niveau max est "<<liste->teteListe->niveauList<<endl;
            if( tmp == NULL)
            return NULL ;
            else
            return tmp ;

        }
}

SCellule* rechercheElementSListeNiveau (SCellule *cellule ,SCellule *cellule_suiv, Elem e  , int niveau)
{
        if ((cellule_suiv== NULL) )
        {
            //cout<<"element non trouve dans la skip-liste "<<endl;
            return NULL ;
        }
        else if (cellule_suiv->info == e)
        {
            //cout<<"element trouver au niveau " <<niveau<< endl;
            return cellule_suiv ;
        }
        else if (cellule_suiv->info > e && (niveau > 0) )
        {
            //cout<<"element non trouve dans de niveau"<<niveau<<endl;
            cellule_suiv=cellule->suivants[niveau-1];
            return rechercheElementSListeNiveau(cellule,cellule_suiv,e ,niveau-1);
        }

        else
        {
            cellule=cellule->suivants[niveau];
            cellule_suiv=cellule->suivants[niveau];
            return rechercheElementSListeNiveau(cellule,cellule_suiv,e,niveau);
        }

}



void insereElement (SListe *liste , Elem e)
{
     SCellule *cellule=initialiserSCellule(e);
        initialiserSCellulePF(cellule);
        insereSCellule(liste,cellule);
}



void insereSCellule (SListe *liste , SCellule *cellule)
{
    // insertion au niveau 0
    int i = cellule->niveauList ;
    if (i>liste->teteListe->niveauList)
        {
            liste->teteListe->niveauList = i ;
        }
    SCellule *cellule_suivante ;
    SCellule *cellule_precedante = liste->teteListe ;

    while (i >= 0)
    {
        cellule_suivante = liste->teteListe->suivants[i] ;
        insereSCelluleNiveau(cellule , cellule_precedante,cellule_suivante,i);
        i-- ;
    }

}



void insereSCelluleNiveau(SCellule *cellule,SCellule *cellule_precedante,SCellule *cellule_suivante , int niv)
{
    if (cellule_suivante== NULL)
    {
        // on insere l' adresse de la cellule
        cellule_precedante->suivants[niv]=cellule;
        if (cellule_precedante->niveauList < cellule->niveauList )
            {
                cellule_precedante->niveauList=cellule->niveauList ;
            }
    }
    else if (cellule->info == 0)
    {
        cellule_precedante->suivants[niv]=cellule ;
        cellule->suivants[niv]=cellule_suivante ;
        if (cellule_precedante->niveauList < cellule->niveauList )
            {
                cellule_precedante->niveauList=cellule->niveauList ;
            }
    }
    else if (cellule->info > cellule_precedante->info && cellule->info < cellule_suivante->info)
    {
        // si l' element a inserer est compris entre cellule suivante et cellule precedeante
        cellule_precedante->suivants[niv]=cellule ;
        cellule->suivants[niv]=cellule_suivante ;
        if (cellule_precedante->niveauList < cellule->niveauList )
            {
                cellule_precedante->niveauList=cellule->niveauList ;
            }
    }
    else if (cellule->info > cellule_suivante->info)
    {
        cellule_precedante=cellule_suivante ;
        cellule_suivante=cellule_precedante->suivants[niv];
        if (cellule_precedante->niveauList < cellule->niveauList )
            {
                cellule_precedante->niveauList=cellule->niveauList ;
            }
        insereSCelluleNiveau(cellule,cellule_precedante,cellule_suivante,niv);
    }
}






void supprimeElementSkiplist (SListe *liste , Elem elem)
{
     if (testSlisteVide(liste))
        {
            cout<<"la liste est vide "<<endl;
        }
    else
        {
            int i = liste->teteListe->niveauList-1 ;
            SCellule *celluleASuprrimer ;
            celluleASuprrimer=rechercheElementSListeNiveau(liste->teteListe,liste->teteListe->suivants[i],elem,i);
            if( celluleASuprrimer== NULL)
            {
                cout<<"l'element" <<elem<<" a supprimer n' est pas dans la liste"<<endl ;
            }
            else
            {
                supprimeSCellule(liste,celluleASuprrimer,celluleASuprrimer->niveauList);
            }
}

}




void supprimeSCellule(SListe *liste , SCellule *celluleASupprimer , int niv)
{
    SCellule *cellule_precedante = liste->teteListe ;
    SCellule *tmp ;
    for (int i=niv-1;i>=0;i--)
    {
        tmp= cellule_precedante->suivants[i];
        while (tmp->info!= celluleASupprimer->info)
        {
            cellule_precedante=tmp;
            tmp=tmp->suivants[i];
        }
        tmp=celluleASupprimer->suivants[i];
        cellule_precedante->suivants[i]=tmp ;
    }

delete celluleASupprimer ;
}
